{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Non-decreasing Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSubsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #递增子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，找出并返回所有该数组中不同的递增子序列，递增子序列中 <strong>至少有两个元素</strong> 。你可以按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,6,7,7]\n",
    "<strong>输出：</strong>[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,4,3,2,1]\n",
    "<strong>输出：</strong>[[4,4]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 15</code></li>\n",
    "\t<li><code>-100 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [non-decreasing-subsequences](https://leetcode.cn/problems/non-decreasing-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [non-decreasing-subsequences](https://leetcode.cn/problems/non-decreasing-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,6,7,7]', '[4,4,3,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]: \n",
    "        def backtracking(nums, startIndex):\n",
    "            if len(path) >=2:\n",
    "                res.append(path.copy())\n",
    "            used = set()# 使用集合对本层元素进行去重\n",
    "            for i in range(startIndex, len(nums)):\n",
    "                if (path and path[-1] > nums[i]) or nums[i] in used:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                used.add(nums[i])\n",
    "                backtracking(nums, i+1)\n",
    "                path.pop()\n",
    "\n",
    "        res = []\n",
    "        path = []\n",
    "        backtracking(nums, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.res = []\n",
    "        self.dfs(nums, 0, [])\n",
    "        print(len(self.res))\n",
    "        return self.res\n",
    "        \n",
    "    def dfs(self, nums, index, path):\n",
    "        if len(path) >= 2 and path not in self.res:\n",
    "            self.res.append(path.copy())\n",
    "        for i in range(index, len(nums)):\n",
    "            if not path or path[-1] <= nums[i]:\n",
    "                path += [nums[i]]\n",
    "                self.dfs(nums, i+1, path)\n",
    "                if path:\n",
    "                    path.pop()\n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        # hashmap + 回溯\n",
    "        hashmap = {}\n",
    "        def backtrack(array):\n",
    "            array.reverse()\n",
    "            for cur in array:\n",
    "                temp = []\n",
    "                for key in hashmap:\n",
    "                    if cur <= key:\n",
    "                        temp.append([cur, key])\n",
    "                        for suf in hashmap[key]:\n",
    "                            temp.append([cur]+suf)\n",
    "                hashmap[cur] = temp\n",
    "        backtrack(nums)\n",
    "        ans = []\n",
    "        for key in hashmap:\n",
    "            ans += hashmap[key]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        cnt = [[] for i in range(len(nums))]\n",
    "        dic = dict()\n",
    "        for i,num in enumerate(nums):\n",
    "            if num in dic:\n",
    "                b = dic[num]\n",
    "            else:\n",
    "                cnt[i].append([num])\n",
    "                b = 0\n",
    "            for j in range(b,i):\n",
    "                if nums[j]<=num:\n",
    "                    for m in cnt[j]:\n",
    "                        cnt[i].append(m[:]+[num])\n",
    "            dic[num] = i\n",
    "        ct = []\n",
    "        for l in cnt:\n",
    "            for m in l:\n",
    "                if len(m)>1:\n",
    "                    ct.append(m)\n",
    "        return ct\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        cnt = [[] for i in range(len(nums))]\n",
    "        dic = dict()\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in dic:\n",
    "                b = dic[num]\n",
    "            else:\n",
    "                cnt[i].append([num])\n",
    "                b = 0\n",
    "            for j in range(b, i):\n",
    "                if nums[j] <= num:\n",
    "                    for m in cnt[j]:\n",
    "                        cnt[i].append(m[:]+[num])\n",
    "            dic[num] = i\n",
    "        return [m for l in cnt for m in l if len(m)>1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        self.res = []\n",
    "        n = len(nums)\n",
    "        def helper(loc,tmp):\n",
    "            if len(tmp) > 1 and tmp not in self.res:\n",
    "                self.res.append(tmp)\n",
    "            for i in range(loc+1,n):\n",
    "                if tmp[-1] <= nums[i]:\n",
    "                    helper(i,tmp+[nums[i]])\n",
    "        for i in range(n):\n",
    "            helper(i,[nums[i]])\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        # pos = 0\n",
    "        # rets = set()\n",
    "        # seqs = []\n",
    "        # self.find_recursively(nums, 0, seqs, rets)\n",
    "        # return list(rets)\n",
    "        # 从尾部往头部计算\n",
    "        rets = set()\n",
    "        single_nums = set()\n",
    "        for i in range(len(nums)):\n",
    "            for item in list(rets):\n",
    "                if nums[i] >= item[-1]:\n",
    "                    rets.add((item) + (nums[i], ))\n",
    "            for item in single_nums:\n",
    "                if nums[i] >= item:\n",
    "                    rets.add((item, ) + (nums[i], ))\n",
    "            single_nums.add(nums[i])\n",
    "        \n",
    "        return list(rets)\n",
    "    \n",
    "    def find_recursively(self, nums, pos, seqs, rets):\n",
    "        \"\"\"太慢了\n",
    "        \"\"\"\n",
    "        if pos > len(nums) - 1:\n",
    "            return\n",
    "        if not seqs:\n",
    "            seqs.append(nums[pos])\n",
    "        else:\n",
    "            if nums[pos] >= seqs[-1]:\n",
    "                seqs.append(nums[pos])\n",
    "                rets.add(tuple([i for i in seqs]))\n",
    "        self.find_recursively(nums, pos+1, [i for i in seqs[:-1]], rets)\n",
    "        self.find_recursively(nums, pos+1, seqs, rets)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        pos = 0\n",
    "        rets = set()\n",
    "        seqs = []\n",
    "        self.find_recursively(nums, 0, seqs, rets)\n",
    "        return list(rets)\n",
    "    \n",
    "    def find_recursively(self, nums, pos, seqs, rets):\n",
    "        \"\"\"没法实现跳跃\n",
    "        \"\"\"\n",
    "        if pos > len(nums) - 1:\n",
    "            return\n",
    "        if not seqs:\n",
    "            seqs.append(nums[pos])\n",
    "        else:\n",
    "            if nums[pos] >= seqs[-1]:\n",
    "                seqs.append(nums[pos])\n",
    "                rets.add(tuple([i for i in seqs]))\n",
    "        self.find_recursively(nums, pos+1, [i for i in seqs[:-1]], rets)\n",
    "        self.find_recursively(nums, pos+1, seqs, rets)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.res = []\n",
    "    def is_up_set(self, arr):\n",
    "        is_up = True\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] < arr[i - 1]:\n",
    "                is_up = False\n",
    "                break\n",
    "        return is_up\n",
    "    def backtracking(self, nums, start_idx):\n",
    "        # 提前收集子集\n",
    "        if len(self.path) >= 2 and self.path not in self.res:\n",
    "            if self.is_up_set(self.path):\n",
    "                self.res.append(self.path[:])\n",
    "        # 终止条件\n",
    "        if not self.is_up_set(self.path) or start_idx == len(nums):\n",
    "            return\n",
    "        # for循环和回溯\n",
    "        for i in range(start_idx, len(nums)):\n",
    "            if self.path and self.path[-1] > nums[i]:\n",
    "                continue\n",
    "            self.path.append(nums[i])\n",
    "            self.backtracking(nums, i + 1)\n",
    "            self.path.pop()\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtracking(nums, 0)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums):\n",
    "        result = set()\n",
    "        n = len(nums)\n",
    "        for i in range(2, n+1):\n",
    "            for c in combinations(nums, i):\n",
    "                if list(c) == sorted(c):\n",
    "                    result.add(c)\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        \n",
    "        def dfs(item, idx):\n",
    "            if len(item)>=2:\n",
    "                if item not in res:\n",
    "                    res.append(item.copy())\n",
    "\n",
    "            for i in range(idx, len(nums)):\n",
    "                if item and nums[i]<item[-1]:\n",
    "                    continue\n",
    "                else:\n",
    "                    item.append(nums[i])\n",
    "                    dfs(item, i+1)\n",
    "                    item.pop()\n",
    "        dfs([],0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        def dfs(nums, begin, path, res):\n",
    "            if len(path) >= 2:\n",
    "                # 转换成 tuple 类型，才可以在结果集中去重\n",
    "                res.append(tuple(path + []))\n",
    "\n",
    "            for i in range(begin, len(nums)):\n",
    "                if i > begin and nums[i] == nums[i - 1]:\n",
    "                    continue\n",
    "                if path and nums[i] < path[-1]:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                dfs(nums, i + 1, path, res)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(nums, 0, [], res)\n",
    "        return list(set(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums):\n",
    "        path = []\n",
    "        res = []\n",
    "        def backtrack(start):\n",
    "            if len(res) >= 2 and len(res) <= len(nums):\n",
    "                if res[-1] >= res[-2] and res not in path:\n",
    "                    path.append(res[:])\n",
    "                else:\n",
    "                    return\n",
    "            used_list = set()\n",
    "            for i in range(start, len(nums)):\n",
    "                if nums[i] not in used_list:\n",
    "                    res.append(nums[i])\n",
    "                    used_list.add(nums[i])\n",
    "                    backtrack(i + 1)\n",
    "                    res.pop()\n",
    "        backtrack(0)\n",
    "        return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "###### 动态规划 ######\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        inc_subseq_hash = collections.defaultdict(list)\n",
    "        for num in nums:\n",
    "            inc_subseq_num = [[num]]\n",
    "            for i in inc_subseq_hash:\n",
    "                if i <= num:\n",
    "                    for inc_subseq in inc_subseq_hash[i]:\n",
    "                        inc_subseq_num.append(inc_subseq + [num])\n",
    "            inc_subseq_hash[num] = inc_subseq_num\n",
    "        res = []\n",
    "        for num in inc_subseq_hash:\n",
    "            for inc_subseq in inc_subseq_hash[num]:\n",
    "                if len(inc_subseq) > 1:\n",
    "                    res.append(inc_subseq)\n",
    "        return res\n",
    "\n",
    "###### 枚举 ######\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = set()\n",
    "        for i in range(1 << len(nums)):\n",
    "            subseq = list()\n",
    "            for j in range(len(nums)):\n",
    "                if i & (1 << j):\n",
    "                    if subseq and nums[j] < subseq[-1]:\n",
    "                        break\n",
    "                    subseq.append(nums[j])\n",
    "            if len(subseq) >= 2:\n",
    "                ans.add(tuple(subseq))\n",
    "        return list(ans)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        def f(x):\n",
    "            for i in range(len(x) - 1):\n",
    "                if x[i] > x[i + 1]:\n",
    "                    return False\n",
    "            return True\n",
    "        res = []\n",
    "        for i in range(2,len(nums) + 1):\n",
    "            for x in combinations(nums,i):\n",
    "                if f(x) and x not in res:\n",
    "                    res.append(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, s: List[int]) -> List[List[int]]:\n",
    "        res=set()\n",
    "        for i in s:\n",
    "            if res:\n",
    "                res|={j+(i,) for j in res if i>=j[-1]}\n",
    "            res.add((i,))\n",
    "        return [j for j in res if len(j)>1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        返回所有数组中不同的递增子序列 (至少有两个元素)\n",
    "        \"\"\"\n",
    "\n",
    "        def backtrack(i, tmp):\n",
    "            # backtrack from nums[i]\n",
    "            if i == len(nums):\n",
    "                if len(tmp) > 1:\n",
    "                    res.append(tmp)\n",
    "                return\n",
    "            \n",
    "            if not tmp or nums[i] >= tmp[-1]:\n",
    "                # 加入大数\n",
    "                backtrack(i+1, tmp + [nums[i]])\n",
    "    \n",
    "            # 当前的元素等于上一个选择的元素的时候，不可以不选择当前元素\n",
    "            # 4 6 7 7 7, 前面的 7 选了之后，后面的 7 一定也得选\n",
    "            if not tmp or tmp[-1] != nums[i]:\n",
    "                backtrack(i+1, tmp)\n",
    "\n",
    "        res = []\n",
    "        backtrack(0, [])\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        self.func1(nums,[],res)\n",
    "        return res\n",
    "\n",
    "    def func1(self,nums,arr1,arr2):\n",
    "        if len(arr1)>=2 and tuple(arr1) not in arr2:\n",
    "                arr2.append(tuple(arr1))\n",
    "        if not nums:\n",
    "            return arr2\n",
    "        for i in range(len(nums)):\n",
    "            if not arr1 or nums[i] >= arr1[-1]:\n",
    "                arr1.append(nums[i])\n",
    "                self.func1(nums[i+1:],arr1[:],arr2)\n",
    "                arr1.pop()\n",
    "        return arr2\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "#         res = set()\n",
    "#         self.func1(nums, [], 0, res)\n",
    "#         return list(res)\n",
    "\n",
    "#     def func1(self, nums, current, start, res):\n",
    "#         if len(current) >= 2:\n",
    "#             res.add(tuple(current))\n",
    "\n",
    "#         for i in range(start, len(nums)):\n",
    "#             if not current or nums[i] >= current[-1]:\n",
    "#                 current.append(nums[i])\n",
    "#                 self.func1(nums, current, i + 1, res)\n",
    "#                 current.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        回溯法\n",
    "        本题的难点在于要去重，但是不能排序\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        result_list = []\n",
    "        path = []\n",
    "\n",
    "        def dfs(start: int = 0):\n",
    "            this_used = set()\n",
    "            if len(path) >= 2:\n",
    "                result_list.append(tuple(path))\n",
    "\n",
    "            for i in range(start, n):\n",
    "                if nums[i] in this_used:\n",
    "                    continue\n",
    "                if len(path) == 0 or nums[i] >= path[-1]:\n",
    "                    path.append(nums[i])\n",
    "                    this_used.add(nums[i])\n",
    "                    dfs(i+1)\n",
    "                    path.pop()\n",
    "\n",
    "        dfs()\n",
    "        return result_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "      ans = set()\n",
    "      for num in nums:\n",
    "        ans.update([(*item, num) for item in ans if item[-1]<=num])\n",
    "        ans.add(tuple([num]))\n",
    "      return [item for item in ans if len(item)>=2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums):\n",
    "        result = []\n",
    "        path = []\n",
    "        self.backtracking(nums, 0, path, result)\n",
    "        return result\n",
    "\n",
    "    def backtracking(self, nums, startIndex, path, result):\n",
    "        if len(path) > 1:\n",
    "            result.append(path[:])  # 注意要使用切片将当前路径的副本加入结果集\n",
    "        \n",
    "        used = [0] * 201  # 使用数组来进行去重操作，题目说数值范围[-100, 100]\n",
    "        for i in range(startIndex, len(nums)):\n",
    "            if (path and nums[i] < path[-1]) or used[nums[i] + 100] == 1:\n",
    "                continue  # 如果当前元素小于上一个元素，或者已经使用过当前元素，则跳过当前元素\n",
    "            \n",
    "            used[nums[i] + 100] = 1  # 标记当前元素已经使用过\n",
    "            path.append(nums[i])  # 将当前元素加入当前递增子序列\n",
    "            self.backtracking(nums, i + 1, path, result)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.cob = []\n",
    "\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtrack(0, nums)\n",
    "        return self.res\n",
    "    \n",
    "    def backtrack(self, start, nums):\n",
    "        if len(self.cob) > 1:\n",
    "            self.res.append(self.cob[:])\n",
    "        used = set()\n",
    "        for i in range(start, len(nums)):\n",
    "            if self.cob and nums[i] < self.cob[-1]:\n",
    "                continue\n",
    "            if nums[i] in used:\n",
    "                continue\n",
    "            used.add(nums[i])\n",
    "            self.cob.append(nums[i])\n",
    "            self.backtrack(i+1, nums)\n",
    "            self.cob.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result=[]\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtracking(nums,0,[])\n",
    "        return self.result\n",
    "    def backtracking(self,nums,start,l):\n",
    "        r=[i for i in l]\n",
    "        if len(r)>=2:\n",
    "            self.result.append(r)\n",
    "\n",
    "        for i in range(start,len(nums)):\n",
    "            if i>start and nums[i] in nums[start:i]:\n",
    "                continue\n",
    "            if not r or nums[i]>=r[-1]:\n",
    "                # if r.count(nums[i])<2:\n",
    "                r.append(nums[i])\n",
    "                self.backtracking(nums,i+1,r)\n",
    "                r.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result=[]\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtracking(nums,0,[])\n",
    "        return self.result\n",
    "    def backtracking(self,nums,start,l):\n",
    "        r=[i for i in l]\n",
    "        if len(r)>=2:\n",
    "            self.result.append(r)\n",
    "\n",
    "        for i in range(start,len(nums)):\n",
    "            if i>start and nums[i] in nums[start:i]:\n",
    "                continue\n",
    "            if not r or nums[i]>=r[-1]:\n",
    "                # if r.count(nums[i])<2:\n",
    "                r.append(nums[i])\n",
    "                self.backtracking(nums,i+1,r)\n",
    "                r.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache, reduce\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')  # 负无穷\n",
    "INFMAX = float('inf')  # 正无穷\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "'''\n",
    "gcd(), ord(), chr(), lower(), upper() 最大公约数/ASCII字符数值/数值ASCII字符/小写/大写\n",
    "startswith(s), endswith(s), find(), index(), count(s)  字符串是否以s开始的/字符串是否以s结尾的/查找返回的是索引/获取索引\n",
    "isalpha(), isdigit(), space(),join()  判断是否全为字符/判断是否全为数字/判断是否为空格/拼接\n",
    "eval() 字符串转换成列表、元组或者字典/\n",
    "uniform(x, y), pow(x, y)# 随机生成下一个实数，它在[x,y]范围内/ x**y 运算后的值。\n",
    "字典推倒式 {key: len(key) for key in list}\n",
    "列表推倒式 [i for i in range(100) if i % 3 == 0] 可切片,可索引,可重复\n",
    "集合推倒式 {i ** 2 for i in (1, 2, 3)}  不可索引,不可切片,不可重复元素\n",
    "'''\n",
    "\n",
    "# 数值和字母进行转换 ord()函数是把字符转换成ASCII码 chr()函数是把ASCII码转换成字符\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "# lcm 最小公倍数 gcd 最大公约数\n",
    "def lcm(x, y):\n",
    "    return x * y // gcd(x, y)\n",
    "\n",
    "# 快速幂\n",
    "def qpow(x, y):\n",
    "    ans = 1\n",
    "    while y:\n",
    "        if y & 1:\n",
    "            ans *= x\n",
    "        x *= x\n",
    "        y >>= 1\n",
    "    return ans\n",
    "\n",
    "# 求组合数\n",
    "def Comb(n, m, p):\n",
    "    a = (factorial(n)) % p\n",
    "    b = (qpow(factorial(m), (p - 2), p)) % p\n",
    "    c = (qpow(factorial(n - m), (p - 2), p)) % p\n",
    "    return a * b * c % p\n",
    "\n",
    "# lucas求组合数\n",
    "def Lucas(n, m, p):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    return Comb(n % p, m % p, p) * Lucas(n // p, m // p, p) % p\n",
    "\n",
    "def rep():\n",
    "    a = list(map(int, input().split()))\n",
    "    return a\n",
    "\n",
    "def sep():\n",
    "    a = input().rstrip('\\n')\n",
    "    return a\n",
    "\n",
    "# --idea \n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/10/19 22:49\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        d = deque([(nums, [])])\n",
    "        while d:\n",
    "            cur, temp = d.popleft()\n",
    "            if len(temp) > 1:\n",
    "                res.append(temp)\n",
    "            s = set()\n",
    "            for i, v in enumerate(cur):\n",
    "                if v in s:\n",
    "                    continue\n",
    "                if not temp or v >= temp[-1]:\n",
    "                    s.add(v)\n",
    "                    d.append((cur[i + 1:], temp + [v]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtracking(self, nums, startindex, path, result, result1):\n",
    "        l = len(nums)\n",
    "        for i in range(1, l):\n",
    "            result1 = []\n",
    "            r1 = self.back(nums, i+1, 0, [], result1)\n",
    "            for index in r1:\n",
    "                if index not in result and index == sorted(index):\n",
    "                    result.append(index)\n",
    "            # result.append(r1[:])\n",
    "        return result\n",
    "\n",
    "    def back(self, nums, length, startindex, path, result1):\n",
    "\n",
    "        if len(path) == length:\n",
    "            result1.append(path[:])\n",
    "            return result1\n",
    "        for i in range(startindex, len(nums)):\n",
    "            path.append(nums[i])\n",
    "\n",
    "            self.back(nums, length, i+1, path, result1)\n",
    "            path.pop()\n",
    "        return result1\n",
    "\n",
    "    def findSubsequences(self, nums):\n",
    "        result = []\n",
    "        result1 = []\n",
    "        # nums = sorted(nums)  # 需要事先对nums数组进行排序\n",
    "        if len(nums) < 2:\n",
    "            return []\n",
    "        self.backtracking(nums, 0, [], result, result1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        seen = set()\n",
    "        \n",
    "        base = 213\n",
    "        mod = int(1e9 + 7)\n",
    "        \n",
    "        def check(i):\n",
    "            res = []\n",
    "            idx = 0\n",
    "            while i:\n",
    "                if i & 1:\n",
    "                    if res and res[-1] > nums[idx]:\n",
    "                        return []\n",
    "                    res.append(nums[idx])\n",
    "                i >>= 1\n",
    "                idx += 1\n",
    "            \n",
    "            if len(res) < 2:\n",
    "                return []\n",
    "            \n",
    "            total = 0\n",
    "            \n",
    "            for n in res:\n",
    "                total = (total * base + n + 101) % mod\n",
    "            \n",
    "            if total in seen:\n",
    "                return []\n",
    "            else:\n",
    "                seen.add(total)\n",
    "                return res\n",
    "            \n",
    "\n",
    "        for i in range(1, 1 << n):\n",
    "            ans = check(i)\n",
    "            \n",
    "            if ans:\n",
    "                res.append(ans)\n",
    "        \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        def bt(nums,paths):\n",
    "            used=[]\n",
    "            res=paths.copy()\n",
    "            for st,path in paths:\n",
    "                for i in range(st, len(nums)):\n",
    "                    if i==len(nums)-1:\n",
    "                        if nums[i] not in used:\n",
    "                            if path==[]:\n",
    "                                used.append(nums[i])\n",
    "                                res.append((i,path+[nums[i]]))\n",
    "                            else:\n",
    "                                if nums[i]>=path[-1]:\n",
    "                                    used.append(nums[i])\n",
    "                                    res.append((i, path + [nums[i]]))\n",
    "                    else:\n",
    "                        if nums[i] not in used:\n",
    "                            if path == []:\n",
    "                                used.append(nums[i])\n",
    "                                res += bt(nums, [(i+1, path+[nums[i]])])\n",
    "                            else:\n",
    "                                if nums[i] >= path[-1]:\n",
    "                                    used.append(nums[i])\n",
    "                                    res += bt(nums, [(i+1, path+[nums[i]])])\n",
    "            return res\n",
    "\n",
    "        def sol(nums):\n",
    "            temp=bt(nums,[(0,[])])\n",
    "            res=[]\n",
    "            for loc,path in  temp:\n",
    "                if len(path)>=2:\n",
    "                    res.append(path)\n",
    "            return res\n",
    "\n",
    "        return sol(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def backtrack(self, nums, index, r):\n",
    "        if index > len(nums):\n",
    "            return \n",
    "        if len(r) >= 2:\n",
    "            self.res.append(list(r))\n",
    "\n",
    "        for i in range(index, len(nums)):\n",
    "            # if nums[i] == prev:\n",
    "            #     continue\n",
    "            # else:\n",
    "            if r and nums[i] < r[-1]:\n",
    "                continue\n",
    "            r.append(nums[i])\n",
    "            self.backtrack(nums, i+1, r)\n",
    "            r.pop()\n",
    "                # prev = nums[i]\n",
    "\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtrack(nums, 0, [])\n",
    "        result = []\n",
    "        for r in self.res:\n",
    "            r = sorted(r)\n",
    "            if r not in result:\n",
    "                result.append(r)\n",
    "        return result\n",
    "        # return self.res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def backtrack(self, nums, index, r, prev):\n",
    "        if index > len(nums):\n",
    "            return \n",
    "        if len(r) >= 2:\n",
    "            self.res.append(list(r))\n",
    "\n",
    "        for i in range(index, len(nums)):\n",
    "            # if r and nums[i] < r[-1]:\n",
    "            #     continue\n",
    "            # r.append(nums[i])\n",
    "            # self.backtrack(nums, i+1, r)\n",
    "            # r.pop()\n",
    "            if r:\n",
    "                if nums[i] >= r[-1]:\n",
    "                    r.append(nums[i])\n",
    "                    self.backtrack(nums, i+1, r, prev)\n",
    "                    r.pop()\n",
    "                    prev = nums[i]\n",
    "            else:\n",
    "                r.append(nums[i])\n",
    "                self.backtrack(nums, i+1, r, prev)\n",
    "                r.pop()\n",
    "\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtrack(nums, 0, [], -200)\n",
    "        result = []\n",
    "        for r in self.res:\n",
    "            r = sorted(r)\n",
    "            if r not in result:\n",
    "                result.append(r)\n",
    "        return result\n",
    "        # return self.res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def backtrack(self, nums, index, r, prev):\n",
    "        if index > len(nums):\n",
    "            return \n",
    "        if len(r) >= 2:\n",
    "            self.res.append(list(r))\n",
    "\n",
    "        for i in range(index, len(nums)):\n",
    "            # if r and nums[i] < r[-1]:\n",
    "            #     continue\n",
    "            # r.append(nums[i])\n",
    "            # self.backtrack(nums, i+1, r)\n",
    "            # r.pop()\n",
    "            if r:\n",
    "                if nums[i] >= r[-1]:\n",
    "                    r.append(nums[i])\n",
    "                    self.backtrack(nums, i+1, r, prev)\n",
    "                    r.pop()\n",
    "                    prev = nums[i]\n",
    "                else:\n",
    "                    continue\n",
    "            else:\n",
    "                r.append(nums[i])\n",
    "                self.backtrack(nums, i+1, r, prev)\n",
    "                # prev = r[0]\n",
    "                r.pop()\n",
    "                prev = nums[i]\n",
    "\n",
    "    def findSubsequences(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtrack(nums, 0, [], -200)\n",
    "        result = []\n",
    "        for r in self.res:\n",
    "            r = sorted(r)\n",
    "            if r not in result:\n",
    "                result.append(r)\n",
    "        return result\n",
    "        # return self.res \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
